Deduplication eliminates duplicate copies of data in storage systems and results in significant space saving. Deduplication can be performed at different granularities, such as at the file, block, or byte (“chunk”) level. Deduplication at each different granularity has different advantages and shortcomings. For example, chunk level deduplication allows for a high level of deduplication, but it also has relatively high metadata overhead. Similarly, block level deduplication may provide slightly lower deduplication than at the chunk level, but usually has less metadata overhead.
Deduplication generally relies on some sort of fingerprinting technique. For example, if two blocks of data are the same, they will have the same fingerprint. Deduplication mechanisms typically store a fingerprint and a pointer to data that is associated with that fingerprint. A duplicate block is found by comparing its fingerprint with existing fingerprints stored by the system. If such a match is found for a block, that block is determined as a potential candidate for deduplication. If no such match is found, then the block cannot be deduplicated. Such blocks whose fingerprints do not match any existing fingerprints in the system will be written to the storage system and their fingerprints will be added to the fingerprint set to be compared in subsequent matches. In some conventional storage systems, all fingerprints are stored in the main memory of the system. As such, a storage system is required to have enough memory to store all valid fingerprints. Although this conventional scheme works well up to a certain extent, it does not work for high capacity systems. This is because the main memory is much more expensive than the secondary (e.g., persistent) storage and cannot expand at the same scale as the secondary storage. For example, such conventional deduplication techniques were either designed for secondary storage or primarily for hard disk drive (HDD) based storage systems. This design also focused on reducing random accesses to HDD's for the purpose of indexing lookups. This was done by dedicating a very high amount of memory, which is expensive, and also it is not always possible to scale the memory of such storage systems to the size needed for storing deduplication data.
One approach to solving this would be to create a B-Tree/radix tree of fingerprints, store the first few levels of the tree(s) (that include fingerprint prefixes) in main memory, and load subsequent levels from persistent storage on demand. In this approach, the top level of the tree(s) may only indicate that a fingerprint with a certain prefix is present within the storage system, but does not indicate anything about the full fingerprint. In such schemes, the loading of leaf level pages from the persistent storage is often required to determine if the desired fingerprint is present at the storage system. Searches for multiple fingerprints will usually traverse different leaf pages and result in significant IO overhead associated with loading deduplication data from the persistent storage into the main memory.